package com.linchong.linkedlist.easy;

import com.linchong.linkedlist.basic.BasicLinkList;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-30 22:33
 * @Description: GetIntersectionNode$相交链表
 *
 * 编写一个程序，找到两个单链表相交的起始节点。
 *
 * 如果两个链表没有交点，返回 null.
 * 在返回结果后，两个链表仍须保持原有的结构。
 * 可假定整个链表结构中没有循环。
 * 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class GetIntersectionNode extends BasicLinkList {
	public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		int m = 0;
		int n = 0;
		ListNode tempA = headA;
		ListNode tempB = headB;
		while(tempA!=null || tempB !=null){
			if(tempA!=null){
				m++;
				tempA = tempA.next;
			}
			if(tempB!=null){
				n++;
				tempB = tempB.next;
			}
		}
		tempA = headA;
		tempB = headB;

		if(m<n){
			int temp = m;
			tempA = headB;
			tempB = headA;
			m = n;
			n = temp;
		}


		ListNode node = null;
		while(tempA!=null && tempB!=null){
			if(m>n){
				m--;
				tempA = tempA.next;
				continue;
			}
			m--;
			n--;
			if(tempA==tempB){
				node = tempA;
				break;
			}
			tempA = tempA.next;
			tempB = tempB.next;
		}
		return node;
	}
}
